Exploiting site%2Dlevel information to improve web search.

Estimating advertisability of tail queries for sponsored search.

Information retrieval challenges in computational advertising.

Measuring the reusability of test collections.
While test collection construction is a time-consuming and expensive process, the true cost is amortized by reusing the collection over hundreds or thousands of experiments. Some of these experiments may involve systems that retrieve documents not judged during the initial construction phase, and some of these systems may be “hard ” to evaluate: depending on which judgments are missing and which judged documents were retrieved, the experimenter’s confidence in an evaluation could potentially be very low. We propose two methods for quantifying the reusability of a test collection for evaluating new systems. The proposed methods provide simple yet highly effective tests for determining whether an existing set of judgments is useful for evaluating a new system. Empirical evaluations using TREC datasets confirm the usefulness of our proposed reusability measures. In particular, we show that our methods can reliably estimate confidence intervals that are indicative of collection reusability.
Automatic generation of bid phrases for online advertising.
One of the most prevalent online advertising methods is textual advertising. To produce a textual ad, an advertiser must craft a short creative (the text of the ad) linking to a landing page, which describes the product or service being promoted. Furthermore, the advertiser must associate the creative to a set of manually chosen bid phrases representing those Web search queries that should trigger the ad. For efficiency, given a landing page, the bid phrases are often chosen first, and then for each bid phrase the creative is produced using a template. Nevertheless, an ad campaign (e.g., for a large retailer) might involve thousands of landing pages and tens or hundreds of thousands of bid phrases, hence the entire process is very laborious. Our study aims towards the automatic construction of online ad campaigns: given a landing page, we propose several algorithmic methods to generate bid phrases suitable for the given input. Such phrases must be both relevant (that is, reflect the content of the page) and well-formed (that is, likely to be used as queries to a Web search engine). To this end, we use a two phase approach. First, candidate bid phrases are generated by a number of methods, including a (monolingual) translation model capable of generating phrases not contained within the text of the input as well as previously “unseen ” phrases. Second, the candidates are ranked in a probabilistic framework using both the translation model, which favors relevant phrases, as well as a bid phrase language model, which favors well-formed phrases. Empirical evaluation based on a real-life corpus of advertisercreated landing pages and associated bid phrases confirms the value of our approach, which successfully re-generates many of the human-crafted bid phrases and performs significantly better than a pure text extraction method. The research described herein was conducted while the first author was a summer intern at Yahoo! Research.
The anatomy of an ad structured indexing and retrieval for sponsored search.

Using landing pages for sponsored search ad selection.

Competing for users%27 attention on the interplay between organic and sponsored search results.

Translating relevance scores to probabilities for contextual advertising.
Information retrieval systems conventionally assess document relevance using the bag of words model. Consequently, relevance scores of documents retrieved for different queries are often difficult to compare, as they are computed on different (or even disjoint) sets of textual features. Many tasks, such as federation of search results or global thresholding of relevance scores, require that scores be globally comparable. To achieve this aim, we propose methods for non-monotonic transformation of relevance scores into probabilities for a contextual advertising selection engine that uses a vector space model. The calibration of the raw scores is based on historical click data.
What happens after an ad click%3F quantifying the impact of landing pages in web advertising.
Unbeknownst to most users, when a query is submitted to a search engine two distinct searches are performed: the organic or algorithmic search that returns relevant Web pages and related data (maps, images, etc.), and the sponsored search that returns paid advertisements. While an enormous amount of work has been invested in understanding the user interaction with organic search, surprisingly little research has been dedicated to what happens after an ad is clicked, a situation we aim to correct. To this end, we define and study the process of context transfer, that is, the user’s transition from Web search to the context of the landing page that follows an ad-click. We conclude that in the vast majority of cases the user is shown one of three types of pages, namely, Homepage (the homepage of the advertiser), Category browse (a browse-able subcatalog related to the original query), and Search transfer (the search results of the same query re-executed on the target site). We show that these three types of landing pages can be accurately distinguished using automatic text classification. Finally, using such an automatic classifier, we correlate the landing page type with conversion data provided by advertisers, and show that the conversion rate (i.e., users ’ response rate to ads) varies considerably according to the type. We believe our findings will further the understanding of users ’ response to search advertising in general, and landing pages in particular, and thus help advertisers improve their Web sites and help search engines select the most suitable ads.
Context transfer in search advertising.

Context transfer in search advertising.

Cross%2Dlanguage query classification using web search for exogenous knowledge.

Nearest%2Dneighbor caching for content%2Dmatch applications.

A search%2Dbased method for forecasting ad impression in contextual advertising.
Contextual advertising (also called content match) refers to the placement of small textual ads within the content of a generic web page. It has become a significant source of revenue for publishers ranging from individual bloggers to major newspapers. At the same time it is an important way for advertisers to reach their intended audience. This reach depends on the total number of exposures of the ad (impressions) and its click-through-rate (CTR) that can be viewed as the probability of an end-user clicking on the ad when shown. These two orthogonal, critical factors are both difficult to estimate and even individually can still be very informative and useful in planning and budgeting advertising campaigns. In this paper, we address the problem of forecasting the number of impressions for new or changed ads in the system.
Online expansion of rare queries for sponsored search.
Sponsored search systems are tasked with matching queries to relevant advertisements. The current state-of-the-art matching algorithms expand the user’s query using a variety of external resources, such as Web search results. While these expansion-based algorithms are highly effective, they are largely inefficient and cannot be applied in real-time. In practice, such algorithms are applied offline to popular queries, with the results of the expensive operations cached for fast access at query time. In this paper, we describe an efficient and effective approach for matching ads against rare queries that were not processed offline. The approach builds an expanded query representation by leveraging offline processing done for related popular queries. Our experimental results show that our approach significantly improves the effectiveness of advertising on rare queries with only a negligible increase in computational cost.
Web Advertising.
Advertising is an important source of income for many websites. To get the attention of the unsuspecting (and probably uninterested) visitors, web advertisements (ads) tend to use elaborate animations and graphics. Depending on the specific technology being used, displaying such ads on the visitor&#039;s screen may require a vast amount of CPU-power. Since present day desktop-CPUs can easily use 100W or more, ads may consume a substantial amount of energy. Although it is important for environmental reasons to reduce energy consumption, increasing the number of ads seems to be counterproductive. The goal of this paper is to investigate the power consumption of web advertisements. For this purpose we used an energy meter to measure the differences in PC power consumption while browsing the web normally (thus with ads enabled), and while browsing with ads being blocked. To simulate normal web browsing, we created a browser-based tool called AutoBrowse, which periodically opens an URL from a predefined list. To block advertisements, we used the Adblock Plus extension for Mozilla Firefox. To measure also power consumption with other browsers, we used in addition the Apache HTTP server and its mod_proxy module to act as an adblocking proxy server. The measurements on several PCs and browsers show that, on average, the additional energy consumption to display web advertisements is 2.5W. To put this number into perspective, we calculated that the total amount of energy used to display web advertisement is equivalent of the total yearly electricity consumption of nearly 2000 households in the Netherlands. It takes 3,6 “average ” wind turbines to generate this amount of energy.
Classifying search queries using the Web as a source of knowledge.
We propose a methodology for building a robust query classification system that can identify thousands of query classes, while dealing in real-time with the query volume of a commercial Web search engine. We use a pseudo relevance feedback technique: given a query, we determine its topic by classifying the Web search results retrieved by the query. Motivated by the needs of search advertising, we primarily focus on rare queries, which are the hardest from the point of view of machine learning, yet in aggregation account for a considerable fraction of search engine traffic. Empirical evaluation confirms that our methodology yields a considerably higher classification accuracy than previously reported. We believe that the proposed methodology will lead to better matching of online ads to rare queries and overall to a better user experience.
Introduction to Computational Advertising.

To swing or not to swing learning when %28not%29 to advertise.
Web textual advertising can be interpreted as a search problem over the corpus of ads available for display in a particular context. In contrast to conventional information retrieval systems, which always return results if the corpus contains any documents lexically related to the query, in Web advertising it is acceptable, and occasionally even desirable, not to show any results. When no ads are relevant to the user’s interests, then showing irrelevant ads should be avoided since they annoy the user and produce no economic benefit. In this paper we pose a decision problem “whether to swing”, that is, whether or not to show any of the ads for the incoming request. We propose two methods for addressing this problem, a simple thresholding approach and a machine learning approach, which collectively analyzes the set of candidate ads augmented with external knowledge. Our experimental evaluation, based on over 28,000 editorial judgments, shows that we are able to predict, with high accuracy, when to“swing”for both content match and sponsored search advertising.
Search advertising using web relevance feedback.

A note on search based forecasting of ad volume in contextual advertising.
In contextual advertising, estimating the number of impressions of an ad is critical in planning and budgeting advertising campaigns. However, producing this forecast, even within large margins of error, is quite challenging. We attack this problem by simulating the presence of a given ad with its associated bid over historical data, involving billions of impressions. This apparently enormous computational task is reduced to a search task involving only the set of distinct pages in the data. Furthermore the search is made more efficient using a two-level search process. Experimental results show that our approach can accurately forecast the expected number of impressions of contextual ads in real time.
Supporting sub%2Ddocument updates and queries in an inverted index.

Cross%2Dlingual query classification a preliminary study.

Optimizing relevance and revenue in ad search a query substitution approach.
The primary business model behind Web search is based on textual advertising, where contextually relevant ads are displayed alongside search results. We address the problem of selecting these ads so that they are both relevant to the queries and profitable to the search engine, showing that optimizing ad relevance and revenue is not equivalent. Selecting the best ads that satisfy these constraints also naturally incurs high computational costs, and time constraints can lead to reduced relevance and profitability. We propose a novel two-stage approach, which conducts most of the analysis ahead of time. An offline preprocessing phase leverages additional knowledge that is impractical to use in real time, and rewrites frequent queries in a way that subsequently facilitates fast and accurate online matching. Empirical evaluation shows that our method optimized for relevance matches a state-of-the-art method while improving expected revenue. When optimizing for revenue, we see even more substantial improvements in expected revenue.
First workshop on targeting and ranking for online advertising.

Contextual advertising by combining relevance with click feedback.
Contextual advertising supports much of the Web’s ecosystem today. User experience and revenue (shared by the site publisher ad the ad network) depend on the relevance of the displayed ads to the page content. As with other document retrieval systems, relevance is provided by scoring the match between individual ads (documents) and the content of the page where the ads are shown (query). In this paper we show how this match can be improved significantly by augmenting the ad-page scoring function with extra parameters from a logistic regression model on the words in the pages and ads. A key property of the proposed model is that it can be mapped to standard cosine similarity matching and is suitable for efficient and scalable implementation over inverted indexes. The model parameter values are learnt from logs containing ad impressions and clicks, with shrinkage estimators being used to combat sparsity. To scale our computations to train on an extremely large training corpus consisting of several gigabytes of data, we parallelize our fitting algorithm in a Hadoop [10] framework. Experimental evaluation is provided showing improved click prediction over a holdout set of impression and click events from a large scale real-world ad placement engine. Our best model achieves a 25 % lift in precision relative to a traditional information retrieval model which is based on cosine similarity, for recalling 10 % of the clicks in our test data.
Relaxation in text search using taxonomies.
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result quality. This new model may be applicable in many arenas, including multifaceted, product, and local search, where documents are augmented with hierarchical metadata such as topic or location. We present efficient algorithms for indexing and query processing in this new retrieval model. We decompose query processing into two sub-problems: first, an online search problem to determine the correct overall level of relaxation cost that must be incurred to generate the top k results; and second, a budgeted relaxation search problem in which all results at a particular relaxation cost must be produced at minimal cost. We show the latter problem is solvable exactly in two hierarchical dimensions, is NP-hard in three or more dimensions, but admits efficient approximation algorithms with provable guarantees. We present experimental results evaluating our algorithms on both synthetic and real data, showing order of magnitude improvements over the baseline algorithm. 1.
Estimating rates of rare events at multiple resolutions.
We consider the problem of estimating occurrence rates of rare events for extremely sparse data, using pre-existing hierarchies to perform inference at multiple resolutions. In particular, we focus on the problem of estimating click rates for (webpage, advertisement) pairs (called impressions) where both the pages and the ads are classified into hierarchies that capture broad contextual information at different levels of granularity. Typically the click rates are low and the coverage of the hierarchies is sparse. To overcome these difficulties we devise a sampling method whereby we analyze a specially chosen sample of pages in the training set, and then estimate click rates using a two-stage model. The first stage imputes the number of (webpage, ad) pairs at all resolutions of the hierarchy to adjust for the sampling bias. The second stage estimates click rates at all resolutions after incorporating correlations among sibling nodes through a tree-structured Markov model. Both models are scalable and suited to large scale data mining applications. On a real-world dataset consisting of 1/2 billion impressions, we demonstrate that even with 95 % negative (non-clicked) events in the training set, our method can effectively discriminate extremely rare events in terms of their click propensity.
Feature selection methods for text classification.
There are numerous text documents available in electronic form. More and more are becoming available every day. Such documents represent a massive amount of information that is easily accessible. Seeking value in this huge collection requires organization; much of the work of organizing documents can be automated through text classification. The accuracy and our understanding of such systems greatly influences their usefulness. In this paper, we seek 1) to advance the understanding of commonly used text classification techniques, and 2) through that understanding, improve the tools that are available for text classification. We begin by clarifying the assumptions made in the derivation of Naive Bayes, noting basic properties and proposing ways for its extension and improvement. Next, we investigate the quality of Naive Bayes parameter estimates and their impact on classification. Our analysis leads to a theorem which gives an explanation for the improvements that can be found in multiclass classification with Naive Bayes using Error-Correcting Output Codes. We use experimental evidence on two commonly-used data sets to exhibit an application of the theorem. Finally, we show fundamental flaws in a commonly-used feature selection algorithm and develop a statistics-based framework for text feature selection. Greater understanding of Naive Bayes and the properties of text allows us to make better use of it in text classification.
Bandits for Taxonomies A Model%2Dbased Approach.
We consider a novel problem of learning an optimal matching, in an online fashion, between two feature spaces that are organized as taxonomies. We formulate this as a multi-armed bandit problem where the arms of the bandit are dependent due to the structure induced by the taxonomies. We then propose a multi-stage hierarchical allocation scheme that improves the explore/exploit properties of the classical multiarmed bandit policies in this scenario. In particular, our scheme uses the taxonomy structure and performs shrinkage estimation in a Bayesian framework to exploit dependencies among the arms, thereby enhancing exploration without losing efficiency on short term exploitation. We prove that our scheme asymptotically converges to the optimal matching. We conduct extensive experiments on real data to illustrate the efficacy of our scheme in practice. 1
Robust classification of rare queries using web knowledge.

A semantic approach to contextual advertising.

On the memory requirements of XPath evaluation over XML streams.
The important challenge of evaluating XPath queries over XML streams has sparked much interest in the past few years. A number of algorithms have been proposed, supporting wider fragments of the query language, and exhibiting better performance and memory utilization. Nevertheless, all the algorithms known to date use a prohibitively large amount of memory for certain types of queries. A natural question then is whether this memory bottleneck is inherent or just an artifact of the proposed algorithms. In this paper we initiate the first systematic and theoretical study of lower bounds on the amount of memory required to evaluate XPath queries over XML streams. We present a general lower bound technique, which given a query, specifies the minimum amount of memory that any algorithm evaluating the query on a stream would need to incur. The lower bounds are stated in terms of new graph-theoretic properties of queries. The proofs are based on tools from communication complexity. We then exploit insights learned from the lower bounds to obtain a new algorithm for XPath evaluation on streams. The algorithm uses space close to the optimum. Our algorithm deviates from the standard paradigm of using automata or transducers, thereby avoiding the need to store large transition tables. 1
Estimating corpus size via queries.

DB2 goes hybrid Integrating native XML and XQuery with relational data and SQL.
This paper presents the overall architecture and design aspects of native XML support in DB2 UDB and its integration with the relational data-flow engine. We describe the new XML components in DB2 UDB and show how XML processing leverages much of the infrastructure which is used for relational data. 
DB2 goes hybrid Integrating native XML and XQuery with relational data and SQL.
This paper presents the overall architecture and design aspects of native XML support in DB2 UDB and its integration with the relational data-flow engine. We describe the new XML components in DB2 UDB and show how XML processing leverages much of the infrastructure which is used for relational data. 
Optimizing cursor movement in holistic twig joins.

Buffering in query evaluation over XML streams.

Buffering in query evaluation over XML streams.

System RX One Part Relational%2C One Part XML.

Statistical Learning Techniques for Costing XML Queries.
Developing cost models for query optimization is significantly  harder for XML queries than for traditional  relational queries. The reason is that XML query  operators are much more complex than relational  operators such as table scans and joins. In this  paper, we propose a new approach, called Comet,  to modeling the cost of XML operators; to our  knowledge, Comet is the first method ever proposed  for addressing the XML query costing problem. As  in relational cost estimation, Comet exploits a set of  system catalog statistics that summarizes the XML  data; the set of &#034;simple path&#034; statistics that we  propose is new, and is well suited to the XML setting.
Querying XML streams.
Streaming algorithms for Xml query answering call for efficient memory management. Tractable queries are distinguished by a bounded number of concurrently alive answer candidates at every time point, and a bounded delay for node selection, for every candidate. We show that both properties are decidable in polynomial time for queries defined by deterministic tree automata. Our results are obtained by reduction to the bounded valuedness problem for recognizable relations between unranked trees, a problem that we show to be decidable in polynomial time. Key words: streaming, tree automata, Xml, databases. 1.
On the Memory Requirements of XPath Evaluation over XML Streams.
The important challenge of evaluating XPath queries over XML streams has sparked much interest in the past few years. A number of algorithms have been proposed, supporting wider fragments of the query language, and exhibiting better performance and memory utilization. Nevertheless, all the algorithms known to date use a prohibitively large amount of memory for certain types of queries. A natural question then is whether this memory bottleneck is inherent or just an artifact of the proposed algorithms. In this paper we initiate the first systematic and theoretical study of lower bounds on the amount of memory required to evaluate XPath queries over XML streams. We present a general lower bound technique, which given a query, specifies the minimum amount of memory that any algorithm evaluating the query on a stream would need to incur. The lower bounds are stated in terms of new graph-theoretic properties of queries. The proofs are based on tools from communication complexity. We then exploit insights learned from the lower bounds to obtain a new algorithm for XPath evaluation on streams. The algorithm uses space close to the optimum. Our algorithm deviates from the standard paradigm of using automata or transducers, thereby avoiding the need to store large transition tables. 1
ROX Relational Over XML.
An increasing percentage of the data needed by business applications is being generated in XML format. Storing the XML in its native format will facilitate new applications that exchange business objects in XML format and query portions of XML documents using XQuery. This paper explores the feasibility of accessing natively-stored XML data through traditional SQL interfaces, called Relational Over XML (ROX), in order to avoid the costly conversion of legacy applications to XQuery. It describes the forces that are driving the industry to evolve toward the ROX scenario as well as some of the issues raised by ROX. The impact of denormalization of data in XML documents is discussed both from a semantic and performance perspective. We also weigh the implications of ROX for manageability and query optimization.
An evaluation of binary XML encoding optimizations for fast stream based xml processing.
This paper provides an objective evaluation of the performance impacts of binary XML encodings, using a fast stream-based XQuery processor as our representative application. Instead of proposing one binary format and comparing it against standard XML parsers, we investigate the individual effects of several binary encoding techniques that are shared by many proposals. Our goal is to provide a deeper understanding of the performance impacts of binary XML encodings in order to clarify the ongoing and often contentious debate over their merits, particularly in the domain of high performance XML stream processing.
Scalable View Expansion in a Peer Mediator System.
To integrate many data sources we use a peer mediator framework where views defined in the peers are logically composed in terms of each other. A common approach to execute queries over mediators is to treat views in data sources as &#039;black boxes&#039;. The mediators locally decompose queries into query fragments and submit them to the data sources for processing. Another approach, used in distributed DBMSs, is to treat the views as &#039;transparent boxes&#039; by importing and fully expanding all views and merge them with the query. The black box approach often leads to inefficient query plans. However, in a peer mediator framework full view expansion (VE) leads to prohibitively long query compilation times when many peers are involved. It also limits peer autonomy since peers must reveal their view definitions. We investigate in a peer mediator framework the tradeoffs between none, partial, and full VE in two different distributed view composition scenarios. We show that it is often favorable with respect to query execution and sometimes even with respect to query compilation time to expand those views having common hidden peer subviews. However, in other cases it is better to use the &#039;black box&#039; approach, in particular when peer autonomy prohibits view importation. Based on this, a hybrid strategy for VE in peer mediators is proposed.
Extracting Relations from XML Documents.
XML is becoming a prevalent format for data exchange. Many XML documents have complex schemas that are not always known, and can vary widely between information sources and applications. In contrast, database applications rely mainly on the flat relational model. We propose a novel, partially supervised approach for extracting userdefined relations from XML documents with unknown schema. The extracted relations can be directly used by an RDBMS, or utilized for information integration or data mining tasks. Our method attempts to automatically capture the lexical and structural features that indicate the relevant portions of the input document, based on a few user-annotated examples. This information can then be used to extract the relation of interest from documents with schemas potentially di#erent from the training examples. We present preliminary experiments showing that our method could be capable of extracting the target relation from XML documents even in the presence of significant variations in the document schemas.
Streaming XPath Processing with Forward and Backward Axes.
We present a streaming algorithm for evaluating XPath expressions that use backward axes (parent and ancestor) and forward axes in a single document-order traversal of an XML document. Other streaming XPath processors handle only forward axes. We show through experiments that our algorithm significantly outperforms (by more than a factor of two) a traditional non-streaming XPath engine. Furthermore, our algorithm scales better because it retains only the relevant portions of the input document in memory. Our engine successfully processes documents over 1GB in size, whereas the traditional XPath engine degrades considerably in performance for documents over 100 MB in size and fails to complete for documents of size over 200 MB. 1
Super%2DFast XML Wrapper Generation in DB2 A Demonstration.

Querying XML data sources in DB2 the XML Wrapper.

Garlic a new flavor of federated query processing for DB2.

Query Decomposition for a Distributed Object%2DOriented Mediator System.
. The mediator-wrapper approachtointegrate data from heterogeneous data sources has usually been centralized in the sense that a single mediator system is placed between a number of data sources and applications. As the number of data sources increases, the centralized mediator architecture becomes an administrative and performance bottleneck. This paper presents a query decomposition algorithm for a distributed mediation architecture where the communication among the mediators is on a higher level than the communication between a mediator and a data source. Some of the salient features of the proposed approach are: #i# exploring query execution schedules that contain data #ow to the sources, necessary when integrating object-oriented sources that provide services #programs# and not only data; #ii# handling of functions with multiple implementations at more than one mediator or source; #iii# multi-phase query decomposition using a combination of heuristics and cost-based strategies; #iv# tree rebalancing by distributed query recompilation.  Keywords: query decomposition, middleware, data integration, distributed databases  1. 
SQL%2FMED %2D A Status Report.

Report on the EDBT%2702 Panel on Scientific Data Integration.

Evaluation of Join Strategies for Distributed Mediation.
Abstract. Three join algorithms are evaluated in an environment with distributed main-memory based mediators and data sources.A streamed ship-out join ships bulks of tuples to a mediator near a data source, followed by post-processing in the client.An extended streamed semi-join in addition builds a main-memory hash index in the client mediator.A ship-in algorithm materializes and joins the data in the client mediator. The first two algorithms are suitable for sources that require parameters to execute a query, as web search engines and computational software, and the last is suitable otherwise.We compare the execution times for obtaining all and the first N tuples, and analyze the percentage time spent in subsystems, varying the network communication speed, bulk size, and data duplicates.The join algorithm leads to orders of magnitude performance difference in different mediation environments. 1
Distributed data integration by object%2Doriented mediator servers.
This paper overviews the data integration system AMOS II based on the wrapper-mediator approach. AMOS II consists of: (i) a mediator database engine that can process and execute queries over data stored locally and in several external data sources, and (ii) object-oriented (OO) multi-database views for reconciliation of data and schema heterogeneities among sources with various capabilities. The data stored in different types of data sources is translated and integrated using OO mediation primitives, providing the user with a consistent view of the data in all the sources. Through its multi-database facilities many distributed AMOS II systems can interoperate in a federation. Since most data reside in the data sources, and to achieve high performance, the core of the system is a main-memory DBMS having a storage manager, query optimizer, transactions, client--server interface, disk backup, etc. The AMOS II data manager is optimized for main-memory access and is extensible so that new d
SQL and Management of External Data.

Distributed View Expansion in Composable Mediators.

Optimizing Queries in Distributed and Composable Mediators.

Distributed Mediation using a Light%2DWeight OODBMS.
An overview is given of a light-weight, Object-Oriented (OO), multi-database system, named AMOS II. Object-Oriented multi-database queries and views can be defined where external data sources of different kinds are translated through AMOS II and integrated through its OO mediation primitives. Through its multi-database facilities many distributed AMOS II systems can interoperate. Since most data reside in the data sources, and to achieve good performance, the system is designed as a main-memory DBMS having a storage manager, query optimizer, transactions, client-server interface, etc. The AMOS II data manager is optimized for main-memory and is extensible so that new data types and query operators can be added or implemented in some external programming language. Such extensibility is essential for data integration. 1 Introduction  The AMOS II system has its roots in the workstation version of the Iris system, WS-Iris [26], and the DAPLEX [34] functional data model. The core of AMOS II...
Distributed Mediation Using a Light%2DWeight OODBMS.
An overview is given of a light-weight, Object-Oriented (OO), multi-database system, named AMOS II. Object-Oriented multi-database queries and views can be defined where external data sources of different kinds are translated through AMOS II and integrated through its OO mediation primitives. Through its multi-database facilities many distributed AMOS II systems can interoperate. Since most data reside in the data sources, and to achieve good performance, the system is designed as a main-memory DBMS having a storage manager, query optimizer, transactions, client-server interface, etc. The AMOS II data manager is optimized for main-memory and is extensible so that new data types and query operators can be added or implemented in some external programming language. Such extensibility is essential for data integration. 1 Introduction  The AMOS II system has its roots in the workstation version of the Iris system, WS-Iris [26], and the DAPLEX [34] functional data model. The core of AMOS II...
Functional Query Optimization over Object%2DOriented Views for Data Integration.
Abstract. AMOS is a mediator system that supports passive (non-intrusive) integration of data from heterogeneous and autonomous data sources. It is based on a functional data model and a declarative functional query language AMOSQL. Foreign data sources, e.g., relational databases, text files, or other types of data sources can be wrapped with AMOS mediators, making them accessible through AMOSQL. AMOS mediators can communicate among each other through the multi-database constructs of AMOSQL that allow definition of functional queries and OO views accessing other AMOS servers. The integrated views can contain both functions and types derived from the data sources. Furthermore, local data associated with these view definitions may be stored in the mediator database. This paper describes AMOS ’ multi-database query facilities and their optimization techniques. Calculus-based function transformations are used to generate minimal query expressions before the query decomposition and cost-based algebraic optimization steps take place. Object identifier (OID) generation is used for correctly representing derived objects in the mediators. A selective OID generation mechanism avoids overhead by generating in the mediator OIDs only for those derived objects that are either needed during the processing of a query or have associated local data in the mediator database. The validity of the derived objects that are assigned OIDs and the completeness of queries to the views are guaranteed by system generated predicates added to the queries. Keywords: heterogeneous data integration, object-oriented views, query optimization 1.
Integrating Heterogenous Overlapping Databases through Object%2DOriented Transformations.
Integration of data from autonomous and heterogeneous  data sources often requires means to  mediate and reconcile overlaps and conflicts between  the integrated data. It is also desirable  that the mediator system stores local data associated  with the data from the sources. Achieving  acceptable query response time for a mediator  system has been a known research problem.  This work presents a mediator query processing  framework based on a representation of the data  mediation and reconciliation by a number of auxiliary  system-defined object-oriented (OO) views  and overloaded functions (queries). The framework  is supported by defining an overloading and  late binding mechanism for the OO views through  declarative queries. A query over the mediated  OO views will have late bound subquery invocations  which are transformed into disjunctive query  expressions. Consistency and completeness of the  queries are guaranteed by expanding the queries  with validation subqueries. Performance is improved  bytype aware query rewrites and selective  OID generation in the mediators. Experiments  show that the proposed query optimization dramatically  improves the query execution time compared  to a naive instance-oriented query strategy  or partial strategies.   
Functional Query Optimization over Object%2DOriented Views for Data Integration.
Abstract. AMOS is a mediator system that supports passive (non-intrusive) integration of data from heterogeneous and autonomous data sources. It is based on a functional data model and a declarative functional query language AMOSQL. Foreign data sources, e.g., relational databases, text files, or other types of data sources can be wrapped with AMOS mediators, making them accessible through AMOSQL. AMOS mediators can communicate among each other through the multi-database constructs of AMOSQL that allow definition of functional queries and OO views accessing other AMOS servers. The integrated views can contain both functions and types derived from the data sources. Furthermore, local data associated with these view definitions may be stored in the mediator database. This paper describes AMOS ’ multi-database query facilities and their optimization techniques. Calculus-based function transformations are used to generate minimal query expressions before the query decomposition and cost-based algebraic optimization steps take place. Object identifier (OID) generation is used for correctly representing derived objects in the mediators. A selective OID generation mechanism avoids overhead by generating in the mediator OIDs only for those derived objects that are either needed during the processing of a query or have associated local data in the mediator database. The validity of the derived objects that are assigned OIDs and the completeness of queries to the views are guaranteed by system generated predicates added to the queries. Keywords: heterogeneous data integration, object-oriented views, query optimization 1.
Calculus%2DBased Transformations of Queries over Object%2DOriented Views in a Database Mediator System.
The concept of object-oriented (OO) views has been a popular approach to data integration. Nevertheless, there have been few reported results on optimization of queries over integrated OO views. In our work, we have developed an OO view system for data integration based on the AMOS database mediator system. The paper describes a system architecture and implementation that takes advantage of query optimization techniques to improve the performance of queries to integrated OO views. The main features of the system are: 1) A passive mediation framework that preserves the autonomy of the data sources. 2) A selective materialization mechanism that minimizes the number of materialized view objects. 3) A predicate based mechanism to guarantee the validity of the materialized view objects as well as the completeness of queries to the view. In order to reduce the overhead of the passive view integration, we use inexpensive calculus based transformations to generate minimal query expressions before the query decomposition and the cost-based algebraic optimization take place.  1. 
Incorporating Association Pattern and Operation Specification in ODMG%27s OQL.

Extending database programming language with declarative querying facilities.
this paper. The work addresses the impedance mismatch problem [1] between the syntax and the semantics of the programming and query language. The query language OVAL is based on the functional query language FQL [3] extending it for the manipulation of complex objects. The salient features of the OVAL query language are: (i) functional nature of the query language, which makes the language suitable for the integration with the procedural programming languages and provides modular style of query definition, (ii) the use of schema information for expressing queries and (iii) recursive evaluation of the algebraic operations on set structured complex objects.
